1. Field
The embodiments relate generally to hierarchical routes and more particularly, to road networks in a computing environment.
2. Background Art
The road network can be represented as a graph with nodes and arcs. A path is a sequence of nodes traversed from a source node to a target node. A cost, such as the travel time, is associated with an arc connecting two nodes. In the case of a road network, the shortest path computation may determine a path whose sum of arc costs is the smallest among all paths between the source and target nodes.
Because a typical graph of a road network may contain millions of nodes, the process to compute the shortest path can be time consuming and computational expensive depending on the computational algorithm utilized. The problem is exacerbated in cases where a system frequently needs to provide several alternative paths to the user. A good candidate of alternate path is a meaningful path that sufficiently differs from the shortest path and other alternates, but may be a bit more expensive. Accordingly, computation of alternates in the road network is even more expensive.
Some conventional systems attempt to address these issues using a bidirectional search: a forward search from the source node and a backward search from the target node. The forward and backward searches meet at an intermediate meeting node between the source and target nodes. An alternate may be the concatenation of two shortest paths: from the source node to the meeting node, and from the meeting node to the target node. Such bidirectional search may result in improved performance and reduced memory consumptions. However, many efficient bidirectional searches that are faster in finding the shortest paths lead to less alternative paths due to the limited number of meeting nodes identified. Therefore, while the conventional systems may be able to quickly find a single shortest path, they fail to efficiently identify an optimal path with adequate alternates in the road network.